package org.example.algorithm.sort;

public class MergeSortAlgorithm extends AbstractSortCommon {
    @Override
    protected <T> void doSort(T arr) {

    }

    public void mergeSort(int[] arr, int start, int end){
        if(arr == null || start >= end) return;
        int mid = ((end - start) >> 1) + start;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start,end, mid);
    }

    public void merge(int[] arr, int start, int end, int mid){
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int index = 0;
        while(i <= mid && j <= mid){
            if(arr[i] > arr[j]){
                temp[index++] = arr[j++];
            }else{
                temp[index++] = arr[i++];
            }
        }
        while(i <= mid) temp[index++] = arr[i++];
        while(j <= end) temp[index++] = arr[j++];
        for(int m = 0; m < index; m++){
            arr[start + m] = temp[m];
        }
        temp = null;
    }

    @Override
    public SortType getSortType() {
        return null;
    }
}
